package 算法基础模板.chapter_01;

import java.util.Scanner;

/**
 * <pre>
 *     {@code
 *
 *void merge_sort(int q[], int l, int r)
 * {
 *     if (l >= r) return;
 *
 *     int mid = l + r >> 1;
 *     merge_sort(q, l, mid);
 *     merge_sort(q, mid + 1, r);
 *
 *     int k = 0, i = l, j = mid + 1;
 *     while (i <= mid && j <= r)
 *         if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
 *         else tmp[k ++ ] = q[j ++ ];
 *
 *     while (i <= mid) tmp[k ++ ] = q[i ++ ];
 *     while (j <= r) tmp[k ++ ] = q[j ++ ];
 *
 *     for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
 * }
 *
 * 作者：yxc
 * 链接：https://www.acwing.com/blog/content/277/
 * 来源：AcWing
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 *
 *     }
 * </pre>
 *
 * @author Summerday
 */
public class MergeSortTemplate {

    static int n;
    static int[] nums;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();

        mergeSort(nums, 0, n - 1);
        for (int num : nums) System.out.print(num + " ");
    }

    static void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int mid = l + r >> 1;
        // 分成子问题
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        // 处理子问题
        int[] temp = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) temp[k++] = nums[i++];
            else temp[k++] = nums[j++];
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= r) temp[k++] = nums[j++];

        // 合并
        for (i = l, j = 0; i <= r; i++, j++) {
            nums[i] = temp[j];
        }
    }
}
